1. Field
The present application relates to the generation of permutations and, more particularly, to generating pseudo-random permutations of a set of indices used for encoding information to be transmitted, such as via a wireless system.
2. Background
In encoding information, such as information to be transmitted in a wireless communication system, it is known to generate different random permutations of a number sequence. The more random the permutation, the more robust the data transmission will be and resilient against errors introduced during transmission of encoded data.
A particular example where permutations are utilized in encoding data includes a turbo encoder, which may be utilized in a wireless transmitter or transceiver, as examples. In particular, FIG. 1 illustrates a turbo encoder 100 that may be utilized in a wireless transceiver. The turbo encoder 100 receives an input of data signals identified by sequence of integers 102 (e.g., {0, 1, 2, . . . , K−1}, where K is an integer). As may be seen in system 100, the sequence 102 is input to an upper convolutional coder 104 that encodes the sequence and outputs the resultant convoluntially encoded sequence to a multiplexer 106. The multiplexer 106 also includes an input 108 to which the unaltered sequence 102 is delivered. Finally, a lower leg includes a permutation generator 110 and a convolutional coder 112 connected in sequence.
In particular, the lower leg of the turbo encoder 100 generates its signals by first permuting the data signals identified by the integer sequence 102 according to a prescribed algorithm or methodology. Examples of known algorithms or methodologies will be discussed later.
After the sequence 102 is permuted by permutation generator 110, a convolutional code is then applied to this permuted sequence by the convolutional coder 112. In the example encoder 100, the data symbols from each of the convolutional coders 104 and 112 and the K data symbols 108 are multiplexed by multiplexer 106 to be output as turbo encoded symbols 114.
As mentioned above, the permutation generator 110 may employ specific algorithms or methodologies for generating different permutations of the sequence 102. One such approach is to generate random permutations using a random number generator to produce the permuted sequence. Accordingly both the encoder and decoder can utilize the same random number generator and a same initial seed number to produce the same sequence. This approach, however, is disadvantageous in that each of the encoder and decoder must store the generated permuted sequence in memory. Accordingly, for large values of K and for a large number of different permutations, the amount of memory required for storing such permutations is costly.
Another approach that is known to generate permutations includes using a rectangular array. As an example, it is assumed that a permutation of numbers from 0 to 9 is desired. These numbers may be written into a rectangular array of a size two rows by five columns (2×5). The numbers zero through nine are then inserted in sequence into the rows and read out from the columns. An exemplary resultant array is illustrated as follows:
0123456789
As may be seen from the array above, a permuted sequence that would be generated by reading out the numbers by columns is {0, 5, 1, 6, 2, 7, 3, 8, 4, 9}. It will be appreciated by those skilled in the art that by choosing arrays of row and column numbers, different permutations can be generated. A disadvantage of this approach, however, is that the resultant sequences may not posses a sufficient degree of randomness, thus not providing a robust permutation.
A further methodology used for generating permutations of a sequence that is known includes use of a linear congruential technique. In particular, in such techniques a number A0 is chosen between 0 and K−1. Next, a recursive function is defined such that An equals (aAn-1+b) mod K for values of n=1, 2, . . . , K−1, where n is an integer. Along with this defined function, a number of conditions must also be met. The first condition is that the values a and b are less than K. Additionally, b must be relatively prime to K. Furthermore, the value (a−1) must be a multiple of p, for every prime number p dividing K. Additionally, the value (a−1) is a multiple of 4 if the value K is also a multiple of 4. Finally, it is desirable that a is relatively prime to K.
As an example of this technique, it is assumed that the value K=9, the prime factor is p is 3, and a value of a is chosen such that (a−1)=3x. Accordingly, if a equals 4 and b equals 7 and A0 equals 5, the generated permuted sequence would be {5, 0, 7, 8, 3, 1, 2, 6, 4}. A drawback to this approach, however, is that for a prime value of K, the only value of a that can be picked is 1. Accordingly, different permutations differ only in the value of A0 and b limiting the randomness that can be achieved.
As another example of a type of encoder known in the art utilizing permutations, FIG. 2 illustrates an encoder 200 utilizing a Low Density Generator Matrix encoder. As illustrated, the system receives an input sequence 202 that is delivered directly to a multiplexer 204 as well as a permuted sequence 206 output from a Low Density Generator Matrix encoder 208. Within the Low Density Generator Matrix encoder 208, coded symbols are generated by parallel concatenation of codes, which, in turn, consist of a permutation of K number of data symbols and a block code that encodes blocks of the permuted sequence. These block code symbols are combined together by the multiplexer 204 after being output in parallel 206 from the low density generator matrix 208. Again, the permutations performed by the low density generator matrix 208 may be effected by any of the known algorithms or methodologies described above. Accordingly, because each of the permutation algorithms or methods discussed has drawbacks, the low density generator matrix 208 accordingly suffers the same drawbacks.